using System;
using System.Linq;
using System.Collections.Generic;

namespace UMC.Data.Caches
{

    class CacheBlock<T>
    {
        class Block
        {
            public int Size;
            public T[] _values = new T[1000];
        }
        int _Size;
        private Block[] _blocks = new Block[10];
        public CacheBlock()
        {
            _blocks[0] = new Block();
            _Size = 1;
        }
        public int Length
        {
            get
            {
                int l = 0;
                for (var i = 0; i < _Size; i++)
                {
                    l += _blocks[i].Size;
                }
                return l;
            }
        }

        public T this[int index]
        {
            get
            {
                int bIndex = 0;
                while (bIndex < _Size)
                {
                    if (_blocks[bIndex].Size > index)
                    {
                        return _blocks[bIndex]._values[index];
                    }
                    else
                    {
                        index -= _blocks[bIndex].Size;
                        bIndex++;
                    }
                }
                return default(T);

            }
            set
            {
                int bIndex = 0;
                while (bIndex < _Size)
                {
                    if (_blocks[bIndex].Size > index)
                    {
                        _blocks[bIndex]._values[index] = value;
                    }
                    else
                    {
                        index -= _blocks[bIndex].Size;
                        bIndex++;
                    }
                }

            }
        }

        public void Insert(int section, int row, T value)
        {
            if (section == _Size)
            {
                if (_Size == _blocks.Length)
                {
                    var bs = new Block[_Size + 6];
                    Array.Copy(this._blocks, 0, bs, 0, _Size);
                    bs[section] = new Block();
                    _blocks = bs;
                }
                else
                {

                    _blocks[section] = new Block();
                }
                _Size++;
            }

            var block = _blocks[section];
            if (block.Size == block._values.Length)
            {
                // section
                var size = block.Size / 2;
                var block2 = new Block();
                var insertSection = section;
                if (row > size)
                {
                    var index = row - size;
                    Array.Copy(block._values, size, block2._values, 0, index);
                    block2._values[index] = value;
                    Array.Copy(block._values, size + index, block2._values, index + 1, size - index);
                    block2.Size = size + 1;
                    insertSection++;
                    block.Size = size;

                }
                else
                {
                    block2.Size = size;
                    Array.Copy(block._values, size, block2._values, 0, size);

                    Array.Copy(block._values, row, block._values, row + 1, size - row);

                    block._values[row] = value;
                    block.Size = size + 1;

                }
                if (_Size == _blocks.Length)
                {
                    var bs = new Block[_Size + 6];
                    Array.Copy(this._blocks, 0, bs, 0, insertSection);
                    bs[insertSection] = block2;
                    Array.Copy(this._blocks, insertSection, bs, 0, _Size - insertSection);
                    _blocks = bs;
                }
                else
                {
                    Array.Copy(this._blocks, insertSection, this._blocks, insertSection + 1, _Size - insertSection);
                    _blocks[insertSection] = block2;
                }
                _Size++;
            }
            else
            {

                Array.Copy(block._values, row, block._values, row + 1, block.Size - row);

                block._values[row] = value;
                block.Size++;
            }

        }
        int SearchSection(int section, T value, IComparer<T> comparer)
        {
            int lo = section;
            int hi = (_Size - section) * 2;
            while (lo <= hi)
            {
                int i = lo + ((hi - lo) >> 1);

                int sec = i / 2;
                T v;
                if ((i & 1) == 0)
                {
                    v = _blocks[sec]._values[_blocks[sec]._values.Length - 1];
                }
                else
                {
                    v = _blocks[sec]._values[0];

                }
                int order = comparer.Compare(v, value);

                if (order == 0) return i;
                if (order < 0)
                {
                    lo = i + 1;
                }
                else
                {
                    hi = i - 1;
                }
            }

            return ~lo;
        }
        public (int, int) Search(int section, int row, int length, T value, IComparer<T> comparer)
        {
            var v = SearchSection(section, value, comparer);
            if (v >= 0)
            {
                int sec = v / 2;

                if ((v & 1) == 0)
                {
                    return (sec, 0);
                }
                else
                {
                    return (sec, _blocks[sec].Size - 1);

                }
                // var se=
            }
            return (1,-1);
            //return -1;
            // var endSection = section;
            // var endRow = row + length;
            // for (; endSection < _Size; endSection++)
            // {
            //     if (_blocks[endSection].Size < endRow)
            //     {
            //         endRow -= _blocks[endSection].Size;
            //     }
            //     else
            //     {
            //         break;
            //     }
            // }



        }
        public int Search(int index, int length, T value, IComparer<T> comparer)
        {

            int lo = index;
            int hi = index + length - 1;
            while (lo <= hi)
            {
                int i = lo + ((hi - lo) >> 1);

                int order = comparer.Compare(this[i], value);

                if (order == 0) return i;
                if (order < 0)
                {
                    lo = i + 1;
                }
                else
                {
                    hi = i - 1;
                }
            }

            return ~lo;
        }
    }

}